home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / SML⁄NJ 93+ / Documentation / examples / stream.sml < prev    next >
Encoding:
Text File  |  1995-12-30  |  1.6 KB  |  54 lines  |  [TEXT/R*ch]

  1. (* stream.sml *)
  2.  
  3. (* streams as a structure *)
  4. (* The type is named stream to avoid conflict with the i/o type stream *)
  5.  
  6. signature STREAM =
  7. sig
  8.   type 'a stream
  9.   val lazyCons: (unit -> '1a * '1a stream) -> '1a stream
  10.   and cons: '1a * '1a stream -> '1a stream
  11.   and head: 'a stream -> 'a
  12.   and tail: 'a stream -> 'a stream
  13.   and prefix : int -> 'a stream -> 'a list
  14.   and lazyMap : ('1a -> '1b) -> '1a stream -> '1b stream
  15. end
  16.  
  17. structure Stream : STREAM =
  18. struct
  19.   datatype 'a stream = STREAM of 'a str ref
  20.        and 'a str = SOLID of 'a * 'a stream
  21.           | SUSPENDED of unit -> ('a * 'a stream);
  22.   fun solidify(STREAM(ref(SOLID p))) = p 
  23.     | solidify(STREAM(s as ref(SUSPENDED f))) =
  24.     let val p = f() in (s := SOLID p; p) end
  25.   fun lazyCons(f) = STREAM(ref(SUSPENDED f))
  26.   fun cons(x,ss) = STREAM(ref(SOLID(x,ss)))
  27.   fun head s = let val (hd,_) = solidify s in hd end
  28.   fun tail s = let val (_,tl) = solidify s in tl end
  29.   fun prefix 0 s = nil
  30.     | prefix n s = (head s)::(prefix (n-1) (tail s))
  31.   fun lazyMap f s =
  32.       let fun g (STREAM(ref(SOLID(x, s)))) = lazyCons(fn () => (f x, g s))
  33.         | g (s) = lazyCons
  34.                (fn () => let val (x, s') = solidify s in (f x, g s') end)
  35.        in lazyCons(fn () => solidify(g s))
  36.       end
  37. end;
  38.  
  39. open Stream;
  40.  
  41. val nats =   (* stream of natural numbers *)
  42.     let fun f n = lazyCons(fn () => (n, f(n+1)));
  43.      in f 0
  44.     end;
  45.  
  46. fun add(s1: int stream, s2: int stream) =
  47.     lazyCons(fn () => (head s1 + head s2, add(tail s1, tail s2)));
  48.  
  49. val fibs =   (* stream of fibonaci numbers *)
  50.     let fun f () = cons(1,lazyCons(fn () =>
  51.                    (1,let val s = f() in add(s, tail s) end)))
  52.      in f ()
  53.     end;
  54.